#include <string>
#include <vector>

using namespace std;

// 相似字符串组
// 如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等
// 那么称 X 和 Y 两个字符串相似
// 如果这两个字符串本身是相等的，那它们也是相似的
// 例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)；
// "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似
// 总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}
// 注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似
// 形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
// 给你一个字符串列表 strs列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。
// 返回 strs 中有多少字符串组
// 测试链接 : https://leetcode.cn/problems/similar-string-groups/

class Solution 
{
    static const int MAXN = 301;
    int sets;
    int father[MAXN];

    void Build(int n)
    {
        sets = n;
        for(int i = 0; i < n; ++i)
        {
            father[i] = i;
        }
    }

    int Find(int i)
    {
        return i == father[i] ? i : father[i] = Find(father[i]);
    }

    void Union(int x, int y)
    {
        int fx = Find(x);
        int fy = Find(y);
        if(fx != fy)
        {
            father[fx] = father[fy];
            --sets;
        }
    }

public:
    int numSimilarGroups(vector<string>& strs) 
    {
        int n = strs.size();
        int m = strs[0].size();
        Build(n);
        for(int i = 0; i < n; ++i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                if(Find(i) != Find(j)) // 不在一个集合才合并
                {
                    int diff = 0;
                    for(int k = 0; k < m && diff < 3; ++k)
                    {
                        if(strs[i][k] != strs[j][k]) ++diff;
                    }
                    if(diff == 0 || diff == 2) Union(i, j); // 相等或者相似都合并
                }
            }
        }
        return sets;
    }
};